package algorithm.leetcode.medium;

/*
 根据一棵树的前序遍历与中序遍历构造二叉树。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/27
 */
public class Question105 {

    public static void main(String[] args) {

    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
        if (pStart == pEnd) {
            // 到了最后长度
            return null;
        }
        // 确定根结点
        int rootVal = preorder[pStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = 0;
        // 在中序遍历中找到根结点的索引
        for (int i = iStart; i < iEnd; i++) {
            if (rootVal == inorder[i]) {
                rootIndex = i;
                break;
            }
        }
        int leftNum = rootIndex - iStart;
        // 递归构造
        root.left = buildTreeHelper(preorder, pStart + 1, pStart + leftNum + 1, inorder, iStart, rootIndex);
        root.right = buildTreeHelper(preorder, pStart + leftNum + 1, pEnd, inorder, rootIndex + 1, iEnd);
        return root;
    }


    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
